#ifndef GRTRAVERSALDFS_H_
#define GRTRAVERSALDFS_H_

#include <vector>

#include "graph_support/GraphSupport.h"

#include "graph_support/alg/traversal/AlwaysTrueFilter.h"

namespace GRAPH_SUPPORT_NS
{
namespace alg
{
namespace traversal
{

template< typename GraphT, typename ForEachFnT, typename FilterT = int >
class DFS
{
private:
	typedef GraphT Graph;
	typedef typename Graph::GrVertex GrVertex;
	typedef typename Graph::GrEdgePtr GrEdgePtr;
	typedef typename Graph::EdgeIterator EdgeIterator;

public:
	DFS( GraphT & gr,
		ForEachFnT forEachFn,
		const FilterT edgesFilter )
		: gr ( gr )
		, forEachFn( forEachFn )
		, edgesFilter( edgesFilter )
		, visited( NULL )
	{
	}

	void dfs( const GrVertex startVertex )
	{
		size_t svId = gr.vert2num( startVertex );
		if ( svId == Graph::NOT_A_VERTEX_ID )
		{
			throw exceptions::GraphOperationException( "Invalin vertex" );
		}
		std::vector< char > visitedBuf( gr.getVertexCount(), ( char ) false );
		visited = ( bool * ) & visitedBuf[0];
		visited[svId] = true;
		privateDfs( svId );
		visited = NULL;
	}

private:
	void privateDfs( size_t v )
	{
		EdgeIterator stopIter = gr.getEdgsEndId( v );
		for ( EdgeIterator it = gr.getEdgsBegId( v ); it != stopIter; ++it )
		{
			GrEdgePtr eptr = * it;
			size_t endId = eptr->endId();
			assert( endId != Graph::NOT_A_VERTEX_ID );
			if ( visited[endId] || ! edgesFilter( eptr ) )
			{
				continue;
			}
			visited[endId] = true;
			forEachFn( eptr );
			privateDfs( endId );
		}
	}

private:
	GraphT & gr;
	ForEachFnT forEachFn;
	const FilterT edgesFilter;
	bool * visited;
};

template< typename GraphT, typename ForEachFnT, typename FilterT >
void GrTraversalDFS( GraphT & gr, typename GraphT::GrVertex startVert,
		ForEachFnT forEachFn,
		const FilterT & edgesFilter )
{
	typedef DFS< GraphT, ForEachFnT, bool ( * ) ( typename GraphT::GrEdgePtr ) > TheDFS;
	TheDFS theDFS( gr, forEachFn, edgesFilter );
	theDFS.dfs( startVert );
}

template< typename GraphT, typename ForEachFnT >
void GrTraversalDFSAllEdges(
		GraphT & gr, typename GraphT::GrVertex startVert,
		ForEachFnT forEachFn )
{
	GrTraversalDFS( gr, startVert, forEachFn, & alwaysTrueFilter< typename GraphT::GrEdgePtr > );
}

}
}
}

#endif /* GRTRAVERSALDFS_H_ */
